import java.util.ArrayList;

/**
 * 
 */

/**
 * @author Dennis Meyer
 * @version 0.0.1
 *
 */
public class BellmanFord 
{
	private int[] distance;
	private int[] previous;
	
	public int[] getDistance()
	{
		return this.distance;
	}
	
	public int[] getPrevios() {
		return this.previous;
	}
	
	// [0] Source, [1] Destination, [2] Weight
	public BellmanFord(int[][] edges, int origin, int countVertex)
	{
		// Initialize Fields
		this.initialize(countVertex);
		
		// Set Source
		this.distance[origin] = 0;
		
		// run Bellman Ford
		for(int i = 1; i < countVertex; i++)
		{
			// Check if weight are changed
			boolean distanceFieldAreUpdated = false;
			
			for (int[] edge : edges)
			{
				if (this.distance[edge[0]] != Integer.MAX_VALUE 
						&& this.distance[edge[0]] + edge[2] < this.distance[edge[2]] )
				{
					this.distance[edge[2]] = this.distance[edge[0]] + edge[2];
					this.previous[edge[2]] = edge[0];
					distanceFieldAreUpdated = true;
				}
			}
			
			if (distanceFieldAreUpdated) return;
		}
	}

	public BellmanFord(ArrayList<int[]> edges, int origin, int countVertex)
	{
		// Initialize Fields
		this.initialize(countVertex);
		
		// Set Source
		this.distance[origin] = 0;
		
		// run Bellman Ford
		for(int i = 1; i < countVertex; i++)
		{
			// Check if weight are changed
			boolean distanceFieldAreUpdated = false;
			
			for (int[] edge : edges)
			{
				if (this.distance[edge[0]] != Integer.MAX_VALUE 
						&& this.distance[edge[0]] + edge[2] < this.distance[edge[1]] )
				{
					this.distance[edge[1]] = this.distance[edge[0]] + edge[2];
					this.previous[edge[1]] = edge[0];
					distanceFieldAreUpdated = true;
				}
			}
			
			if (distanceFieldAreUpdated) return;
		}
	}
	
	private void initialize(int countVertex)
	{
		this.distance = new int[countVertex];
		this.previous = new int[countVertex];
		
		// Initialize Distance and Previous Field
		for(int i = 0; i < countVertex; i++)
		{
			this.distance[i] = Integer.MAX_VALUE;
			this.previous[i] = -1;
		}
	}
}
